GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Rabin-Kryptosystem</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Rabin-Kryptosystem</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Das Rabin-Kryptosystem ist innerhalb der <a href="Kryptologie" title="Kryptologie">Kryptologie</a> ein <a href="Asymmetrisches_Kryptosystem" title="Asymmetrisches Kryptosystem">asymmetrisches Kryptosystem</a>, dessen Sicherheit <a href="Beweisbare_Sicherheit" title="Beweisbare Sicherheit">beweisbar</a> auf dem <a href="Faktorisierungsproblem" class="mw-redirect" title="Faktorisierungsproblem">Faktorisierungsproblem</a> beruht und das mit <a href="RSA-Kryptosystem" title="RSA-Kryptosystem">RSA</a> verwandt ist. Es lässt sich auch zur <a href="Elektronische_Signatur" title="Elektronische Signatur">Signatur</a> verwenden. In der Praxis findet das Verfahren allerdings kaum Anwendung. Die Entschlüsselung ist nicht eindeutig, da es mehrere, in der Regel vier Lösungen für x der Gleichung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y=x^{2}{\bmod {n}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y=x^{2}{\bmod {n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ca1586a0776d3c5c60ff1e73d0be0e0b26473537.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.714ex; height:3.009ex;" alt="{\displaystyle y=x^{2}{\bmod {n}}}" loading="lazy"> gibt.

<div class="mw-heading mw-heading2"><h2 id="Geschichte">Geschichte</h2></div>

Das Verfahren wurde im Januar <a href="1979" title="1979">1979</a> von <a href="Michael_O._Rabin" title="Michael O. Rabin">Michael O. Rabin</a> veröffentlicht. Das Rabin-Kryptosystem war das erste <a href="Asymmetrisches_Kryptosystem" title="Asymmetrisches Kryptosystem">asymmetrische Kryptosystem</a>, bei dem auf mathematischem Weg bewiesen werden konnte, dass es zumindest gleich schwierig zu lösen ist wie das <a href="Faktorisierungsverfahren" title="Faktorisierungsverfahren">Faktorisierungsproblem</a> (das als nicht effizient lösbar angenommen wird).

<div class="mw-heading mw-heading2"><h2 id="Schlüsselerzeugung">Schlüsselerzeugung</h2></div>

Wie alle <a href="Asymmetrisches_Kryptosystem" title="Asymmetrisches Kryptosystem">asymmetrischen Kryptosysteme</a> verwendet auch das Rabin-Kryptosystem einen <a href="%C3%96ffentlicher_Schl%C3%BCssel" class="mw-redirect" title="Öffentlicher Schlüssel">öffentlichen Schlüssel</a> (Public Key) und einen <a href="Geheimer_Schl%C3%BCssel" class="mw-redirect" title="Geheimer Schlüssel">geheimen Schlüssel</a> (Private Key). Der Öffentliche dient der Verschlüsselung und kann ohne Bedenken veröffentlicht werden, während der geheime Schlüssel der Entschlüsselung dient und nur den Empfängern der Nachricht bekannt sein darf.

Es folgt nun eine genaue mathematische Beschreibung der Schlüsselerzeugung:

Seien <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p,q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p,q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/953a97b9fe7d257c9666fb3cf6bf75380295e2cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:3.362ex; height:2.009ex;" alt="{\displaystyle p,q}" loading="lazy"> zwei möglichst große <a href="Primzahl" title="Primzahl">Primzahlen</a>, häufig kurz als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p,q\in \mathbb {P} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p,q\in \mathbb {P} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2cf925c5a3253357a8323a09e2c693863617e59b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:7.623ex; height:2.509ex;" alt="{\displaystyle p,q\in \mathbb {P} }" loading="lazy"> geschrieben, für die eine bestimmte <a href="#Kongruenzbedingung">Kongruenzbedingung</a> gelten muss. Der <a href="%C3%96ffentlicher_Schl%C3%BCssel" class="mw-redirect" title="Öffentlicher Schlüssel">öffentliche Schlüssel</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> wird durch Multiplikation der beiden Zahlen erzeugt, also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=p\cdot q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=p\cdot q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7d68e74657cbf5af7207548b1e0ac94896d28b88.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.411ex; height:2.009ex;" alt="{\displaystyle n=p\cdot q}" loading="lazy">. Der <a href="Geheimer_Schl%C3%BCssel" class="mw-redirect" title="Geheimer Schlüssel">geheime Schlüssel</a> ist das Paar <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (p,q)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (p,q)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9769c58523b9b639866a2d48e657d9c26911143a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.082ex; height:2.843ex;" alt="{\displaystyle (p,q)}" loading="lazy">. Anders ausgedrückt: Wer nur <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> kennt, kann ver- aber nicht entschlüsseln, wer dagegen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"> kennt, kann damit auch entschlüsseln. Wären <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"> keine Primzahlen, so ließe sich das Verfahren nicht anwenden.

Beispiel:

Wenn man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p=7}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p=7}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/217ef46e3770ee77e0adfff10c46717d16432c4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:5.52ex; height:2.509ex;" alt="{\displaystyle p=7}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q=11}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q=11}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/659ce28305cdf56defcd131414b373f5080e7418.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.493ex; height:2.509ex;" alt="{\displaystyle q=11}" loading="lazy"> annimmt, dann ergibt sich daraus der öffentliche Schlüssel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=p\cdot q=77}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=p\cdot q=77}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7aaca4847067c6118624e8d0ff11cd2c401bb9b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.835ex; height:2.509ex;" alt="{\displaystyle n=p\cdot q=77}" loading="lazy">. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 7}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 7}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ee716ec61382a6b795092c0edd859d12e64cbba8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 7}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 11}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 11}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/da6aabe7c6af49fe640b2d401cb2dbe909bb7475.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 11}" loading="lazy"> sind gültige Zahlen, weil sie Primzahlen sind und die Kongruenzbedingung für sie gilt.

In Wirklichkeit werden viel größere Zahlen verwendet, um die Entschlüsselung durch Dritte schwierig zu machen (Primzahlen in der Größenordnung von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 10^{200}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 10^{200}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92867e200a6ef2c7b0f1c4b80e6e5ab7108d2114.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.023ex; height:2.676ex;" alt="{\displaystyle 10^{200}}" loading="lazy"> und größer).

<div class="mw-heading mw-heading2"><h2 id="Kongruenzbedingung">Kongruenzbedingung</h2></div>

Im Rabin-Kryptosystem werden die Primzahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"> normalerweise so gewählt, dass die

Kongruenzbedingung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\equiv q\equiv 3{\pmod {4}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p\equiv q\equiv 3{\pmod {4}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/45d0c2a817da5d0a47e79e0094849212b44664b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:20.534ex; height:2.843ex;" alt="{\displaystyle p\equiv q\equiv 3{\pmod {4}}}" loading="lazy"> gilt.

Diese Bedingung vereinfacht und beschleunigt die Entschlüsselung.

Allgemein gilt nämlich: Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> eine Primzahl mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\equiv 3{\pmod {4}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r\equiv 3{\pmod {4}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7e837b7debd07baacc929a7668523027b18759cb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.156ex; height:2.843ex;" alt="{\displaystyle r\equiv 3{\pmod {4}}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\in \mathbb {Z} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\in \mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/175ebd03e0644b0967a63d648c2843a5e883257b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.621ex; height:2.176ex;" alt="{\displaystyle a\in \mathbb {Z} }" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\equiv b^{2}{\pmod {r}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\equiv b^{2}{\pmod {r}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8e9f2497ef39e8a38bf9c7fe2d65c425a069f90c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.113ex; height:3.176ex;" alt="{\displaystyle a\equiv b^{2}{\pmod {r}}}" loading="lazy">, dann findet man eine Quadratwurzel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> mit

<msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\equiv a^{\frac {r+1}{4}}{\pmod {r}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/99f22c4ef6a79e8f34d3ee43307a10b65eb1d8e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.527ex; height:4.176ex;" alt="{\displaystyle s\equiv a^{\frac {r+1}{4}}{\pmod {r}}}" loading="lazy">.</dd></dl>

Es gilt also

<msup>

</mrow>

</msup>

<msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s^{2}\equiv a^{\frac {r+1}{2}}\equiv b^{r+1}\equiv b^{2}\equiv a{\pmod {r}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b440c47cc7e07628a22cdfe04d7faae86616ce4f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:37.23ex; height:4.176ex;" alt="{\displaystyle s^{2}\equiv a^{\frac {r+1}{2}}\equiv b^{r+1}\equiv b^{2}\equiv a{\pmod {r}}}" loading="lazy"></dd></dl>

wegen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b^{r-1}\equiv 1{\pmod {r}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b^{r-1}\equiv 1{\pmod {r}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dab6f5641c15a2e3f69c516062537030abaaf801.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.065ex; height:3.176ex;" alt="{\displaystyle b^{r-1}\equiv 1{\pmod {r}}}" loading="lazy"> nach dem <a href="Kleiner_fermatscher_Satz" title="Kleiner fermatscher Satz">kleinen Fermatschen Satz</a>.

Da <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> eine Primzahl ist, gilt zudem entweder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s\equiv b{\pmod {r}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\equiv b{\pmod {r}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fa014584a85bb4af9c239e97ed6fc738951f5c11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.919ex; height:2.843ex;" alt="{\displaystyle s\equiv b{\pmod {r}}}" loading="lazy"> oder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s\equiv -b{\pmod {r}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\equiv -b{\pmod {r}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fb681145d19342fb4dd7463e0562e0e7bece09ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.727ex; height:2.843ex;" alt="{\displaystyle s\equiv -b{\pmod {r}}}" loading="lazy">.

Wegen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 7\equiv 11\equiv 3{\pmod {4}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 7\equiv 11\equiv 3{\pmod {4}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3f3c6bf476bc55f0f759356f3729e5eb77db48e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.693ex; height:2.843ex;" alt="{\displaystyle 7\equiv 11\equiv 3{\pmod {4}}}" loading="lazy"> ist die Kongruenzbedingung im Beispiel bereits erfüllt.

<div class="mw-heading mw-heading2"><h2 id="Verschlüsselung">Verschlüsselung</h2></div>

Mit dem Rabin-Verfahren lassen sich beliebige <a href="Klartext_(Kryptographie)" title="Klartext (Kryptographie)">Klartexte</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> aus der Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{0,\ldots ,n-1\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{0,\ldots ,n-1\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/42c79e3cb72eea59a323c64b7aa568b85e4f5dc5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.063ex; height:2.843ex;" alt="{\displaystyle \{0,\ldots ,n-1\}}" loading="lazy"> verschlüsseln. Alice, die einen solchen Klartext verschlüsseln will, muss dazu nur den öffentlichen Schlüssel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> des Empfängers Bob kennen. Sie berechnet dann den <a href="Geheimtext" title="Geheimtext">Geheimtext</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> nach der Formel

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\equiv m^{2}{\pmod {n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/41dcb0a454a6e71256fd4e16a5bf4599e38bde3a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.279ex; height:3.176ex;" alt="{\displaystyle c\equiv m^{2}{\pmod {n}}}" loading="lazy"></dd></dl>

Im praktischen Einsatz bietet sich die Verwendung von <a href="Blockchiffre" class="mw-redirect" title="Blockchiffre">Blockchiffre</a> an.

In unserem Beispiel sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=\{0,...,76\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=\{0,...,76\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a673de1d9cc0dc4277b4218264f898630a7b17f7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.826ex; height:2.843ex;" alt="{\displaystyle P=\{0,...,76\}}" loading="lazy"> der Klartextraum, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=20}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=20}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/003f58fd782a8ea62aa011defdf402a9567f4f42.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.464ex; height:2.176ex;" alt="{\displaystyle m=20}" loading="lazy"> der Klartext. Der Geheimtext ist hierbei nun <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\equiv m^{2}{\pmod {n}}\equiv 15{\pmod {n}}}">

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\equiv m^{2}{\pmod {n}}\equiv 15{\pmod {n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dba8d0a0df0f667626204191b57a61939a60d0cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.781ex; height:3.176ex;" alt="{\displaystyle c\equiv m^{2}{\pmod {n}}\equiv 15{\pmod {n}}}" loading="lazy">.

Dabei muss man beachten, dass für genau vier verschiedene <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> das <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> den Wert 15 aufweist, nämlich für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\in \{13,20,57,64\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\in \{13,20,57,64\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/49873abe353c533c51d1ab1e051c7eaed92ffcb5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.607ex; height:2.843ex;" alt="{\displaystyle m\in \{13,20,57,64\}}" loading="lazy">. Jeder <a href="Quadratischer_Rest" title="Quadratischer Rest">quadratische Rest</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> hat genau vier verschiedene Quadratwurzeln modulo <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=pq}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=pq}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/edd7540bf012670052b38c45bf043b5c8e6cd159.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.732ex; height:2.009ex;" alt="{\displaystyle n=pq}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Entschlüsselung">Entschlüsselung</h2></div>

Bei der <a href="Entschl%C3%BCsselung" title="Entschlüsselung">Entschlüsselung</a> wird aus dem <a href="Geheimtext" title="Geheimtext">Geheimtext</a> unter Verwendung des <a href="Geheimer_Schl%C3%BCssel" class="mw-redirect" title="Geheimer Schlüssel">geheimen Schlüssels</a> wieder der <a href="Klartext_(Kryptographie)" title="Klartext (Kryptographie)">Klartext</a> berechnet.

Das genaue mathematische Vorgehen wird nun beschrieben:

Seien allgemein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> bekannt, gesucht wird <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\in \{0,...,n-1\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\in \{0,...,n-1\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/84c58830907977082c8df0a61f9e3c69bd529361.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.936ex; height:2.843ex;" alt="{\displaystyle m\in \{0,...,n-1\}}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m^{2}\equiv c\,{\pmod {r}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m^{2}\equiv c\,{\pmod {r}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c4ca1e3a7123cfedcbfabe9444559316b6748b99.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.32ex; height:3.176ex;" alt="{\displaystyle m^{2}\equiv c\,{\pmod {r}}}" loading="lazy">. Für zusammengesetzte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> (beispielsweise unsere <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">) existiert kein effizientes Verfahren zur Bestimmung von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">. Bei einer Primzahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\in \mathbb {P} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r\in \mathbb {P} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/66760469f4eff5b54715989054c921d08edb69c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.31ex; height:2.176ex;" alt="{\displaystyle r\in \mathbb {P} }" loading="lazy"> (in unserem Fall <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy">) lässt sich jedoch der <a href="Chinesischer_Restsatz" title="Chinesischer Restsatz">chinesische Restsatz</a> ausnutzen.

In unserem Fall sind nun <a href="Quadratwurzel" title="Quadratwurzel">Quadratwurzeln</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{p},m_{q}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{p},m_{q}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7df4738432761b9d03ca57ea045e719559d47ca0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.162ex; height:2.343ex;" alt="{\displaystyle m_{p},m_{q}}" loading="lazy"> gesucht:

</mrow>

</mrow>

</msubsup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{p}^{2}\equiv c{\pmod {p}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5fd2e750a821abdfd7060eab5f324301bcba0d3a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:18.058ex; height:3.176ex;" alt="{\displaystyle m_{p}^{2}\equiv c{\pmod {p}}}" loading="lazy"></dd></dl>

und

</mrow>

</mrow>

</msubsup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{q}^{2}\equiv c{\pmod {q}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e3997ddd4586cd241ad6c9df88212612e527d46e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.954ex; height:3.009ex;" alt="{\displaystyle m_{q}^{2}\equiv c{\pmod {q}}}" loading="lazy"></dd></dl>

Wegen obiger Kongruenzbedingung können wir wählen:

<msub>

</mrow>

</msub>

<msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{p}\equiv c^{\frac {p+1}{4}}{\pmod {p}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/30846f5e97b3fc715b82ecbd8503debe2fe653fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:21.503ex; height:4.509ex;" alt="{\displaystyle m_{p}\equiv c^{\frac {p+1}{4}}{\pmod {p}}}" loading="lazy"></dd></dl>

und

<msub>

</mrow>

</msub>

<msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{q}\equiv c^{\frac {q+1}{4}}{\pmod {q}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b5175395008f8850d358bc717af2c91783b65e55.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:21.276ex; height:4.509ex;" alt="{\displaystyle m_{q}\equiv c^{\frac {q+1}{4}}{\pmod {q}}}" loading="lazy">.</dd></dl>

In unserem Beispiel ergeben sich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{p}=1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{p}=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bbbaa7f94c989d0bf8e00d3b9c0778c447e6ec88.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.36ex; height:2.843ex;" alt="{\displaystyle m_{p}=1}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{q}=9}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{q}=9}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c7f19b008b8dadf4794f69aa5edf826f3727b00b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.29ex; height:2.843ex;" alt="{\displaystyle m_{q}=9}" loading="lazy">.

Mit Hilfe des <a href="Erweiterter_euklidischer_Algorithmus" title="Erweiterter euklidischer Algorithmus">erweiterten euklidischen Algorithmus</a> werden nun <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{p},y_{q}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{p},y_{q}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/50c94ef34c97e592b69c01ae6ca73eeb8ae0b993.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.36ex; height:2.343ex;" alt="{\displaystyle y_{p},y_{q}}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{p}\cdot p+y_{q}\cdot q=1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{p}\cdot p+y_{q}\cdot q=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9a7c170705a66630105693def5a078794a2c6dcc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.025ex; height:2.843ex;" alt="{\displaystyle y_{p}\cdot p+y_{q}\cdot q=1}" loading="lazy"> bestimmt. In unserem Beispiel erhalten wir <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{p}=-3,y_{q}=2}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{p}=-3,y_{q}=2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/138b07b688e67a5a69d98c9135ed899fe43bb66e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.69ex; height:2.843ex;" alt="{\displaystyle y_{p}=-3,y_{q}=2}" loading="lazy">.

Nun werden unter Ausnutzung des <a href="Chinesischer_Restsatz" title="Chinesischer Restsatz">chinesischen Restsatzes</a> die vier Quadratwurzeln <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle +r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle +r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3b538ab3f415e7d58ba36cf92bb38878838af4c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:2.857ex; height:2.176ex;" alt="{\displaystyle +r}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c4daf0fc6913ad6959b59e4fd218e451e14d07e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:2.857ex; height:2.176ex;" alt="{\displaystyle -r}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle +s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle +s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/eebaae22615f5c7b463ecbfbfff458da9568997e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:2.899ex; height:2.176ex;" alt="{\displaystyle +s}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b9a32c98ed353b6578c899e74337ccca3a451ec1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:2.899ex; height:2.176ex;" alt="{\displaystyle -s}" loading="lazy"> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c+n\mathbb {Z} \in \mathbb {Z} /n\mathbb {Z} }">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c+n\mathbb {Z} \in \mathbb {Z} /n\mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/adbcd974a405af23288738da9799ef5acf99e07d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.291ex; height:2.843ex;" alt="{\displaystyle c+n\mathbb {Z} \in \mathbb {Z} /n\mathbb {Z} }" loading="lazy"> berechnet (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} /n\mathbb {Z} }">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} /n\mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f2120ebbc85f91df66c6de5446367bf9fd620844.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.658ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} /n\mathbb {Z} }" loading="lazy"> steht hierbei wie üblich für die <a href="Menge_(Mathematik)" title="Menge (Mathematik)">Menge</a> der <a href="Restklasse" title="Restklasse">Restklassen</a> modulo <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">; die vier Quadratwurzeln liegen in der Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{0,...,n-1\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{0,...,n-1\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/269d3adcaf4c166d51adbff7085f51e1a36d5e19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.055ex; height:2.843ex;" alt="{\displaystyle \{0,...,n-1\}}" loading="lazy">):

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}r&=(y_{p}\cdot p\cdot m_{q}+y_{q}\cdot q\cdot m_{p}){\pmod {n}}\\-r&=n-r\\s&=(y_{p}\cdot p\cdot m_{q}-y_{q}\cdot q\cdot m_{p}){\pmod {n}}\\-s&=n-s\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/27118d35de22c68a27b3eb1ebc4306c97849f9f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.505ex; width:41.887ex; height:12.176ex;" alt="{\displaystyle {\begin{aligned}r&=(y_{p}\cdot p\cdot m_{q}+y_{q}\cdot q\cdot m_{p}){\pmod {n}}\\-r&=n-r\\s&=(y_{p}\cdot p\cdot m_{q}-y_{q}\cdot q\cdot m_{p}){\pmod {n}}\\-s&=n-s\end{aligned}}}" loading="lazy"></dd></dl>

Eine dieser Quadratwurzeln <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mod \,n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mod \,n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9ca91b6a9517a1b721025a783114326efe3cd137.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.657ex; height:2.176ex;" alt="{\displaystyle \mod \,n}" loading="lazy"> ist wieder der anfängliche Klartext <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">. Im Beispiel gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\in \{64,\mathbf {20} ,13,57\}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\in \{64,\mathbf {20} ,13,57\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4c81271225519b8aa6774d35407e424189ece6dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.956ex; height:2.843ex;" alt="{\displaystyle m\in \{64,\mathbf {20} ,13,57\}}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Bewertung">Bewertung</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Effektivität">Effektivität</h3></div>

Die Entschlüsselung liefert zusätzlich zum Klartext drei weitere Ergebnisse, das richtige Ergebnis muss daher erraten werden. Dies ist der große Nachteil des Rabin-Kryptosystems.

Man kann aber Klartexte mit spezieller Struktur wählen. Hierdurch geht jedoch die Äquivalenz zum Faktorisierungsproblem verloren, wie sich zeigen lässt. Das System wird dadurch also geschwächt.

<div class="mw-heading mw-heading3"><h3 id="Effizienz">Effizienz</h3></div>

Bei der Verschlüsselung muss eine Quadrierung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mod \,n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mod \,n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9ca91b6a9517a1b721025a783114326efe3cd137.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.657ex; height:2.176ex;" alt="{\displaystyle \mod \,n}" loading="lazy"> durchgeführt werden. Das ist effizienter als <a href="RSA-Kryptosystem" title="RSA-Kryptosystem">RSA</a> mit dem Exponenten 3.

Die Entschlüsselung erfordert die Anwendung des <a href="Chinesischer_Restsatz" title="Chinesischer Restsatz">chinesischen Restsatzes</a> und je eine <a href="Modulare_Exponentiation" class="mw-redirect" title="Modulare Exponentiation">modulare Exponentiation</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mod \,p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mod \,p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f53e644728909310c064574e47f90a02c7aa09f2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.431ex; height:2.509ex;" alt="{\displaystyle \mod \,p}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mod \,q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mod \,q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ecf89b8098f53ddaa2483ccd05ce31df46a0670.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.331ex; height:2.509ex;" alt="{\displaystyle \mod \,q}" loading="lazy">. Die Effizienz der Entschlüsselung ist mit <a href="RSA-Kryptosystem" title="RSA-Kryptosystem">RSA</a> vergleichbar.

<div class="mw-heading mw-heading3"><h3 id="Sicherheit">Sicherheit</h3></div>

Der große Vorteil des Rabin-Kryptosystems ist, dass man es nur dann brechen kann, wenn man das beschriebene <a href="Faktorisierungsproblem" class="mw-redirect" title="Faktorisierungsproblem">Faktorisierungsproblem</a> effizient lösen kann.

Anders als etwa bei <a href="RSA-Kryptosystem" title="RSA-Kryptosystem">RSA</a> lässt sich zeigen, dass das Rabin-Kryptosystem genauso schwer zu brechen ist wie das Faktorisierungsproblem, auf dem es beruht. Es ist somit sicherer. Wer also das Rabin-Verfahren brechen kann, der kann auch das Faktorisierungsproblem lösen und umgekehrt. Es gilt daher als sicheres Verfahren, solange das Faktorisierungsproblem ungelöst ist. Vorausgesetzt ist dabei wie bereits beschrieben aber, dass die Klartexte keine bestimmte Struktur aufweisen.

Da man auch außerhalb der Kryptologie bemüht ist Faktorisierungsprobleme zu lösen, würde sich eine Lösung rasch in der Fachwelt verbreiten. Doch das ist bislang nicht geschehen. Man kann also davon ausgehen, dass das zugrundeliegende Faktorisierungsproblem derzeit unlösbar ist. Ein Angreifer, der nur belauscht, wird daher derzeit nicht in der Lage sein, das System zu brechen.

Ein aktiver Angreifer aber kann das System mit einem <a href="Chosen-Ciphertext-Angriff" title="Chosen-Ciphertext-Angriff">Angriff mit frei wählbarem Geheimtext</a> (englisch chosen-ciphertext attack) brechen, wie sich mathematisch zeigen lässt. Aus diesem Grund findet das Rabin-Kryptosystem in der Praxis kaum Anwendung.

Durch Hinzufügen von Redundanz, z. B. Wiederholen der letzten 64 Bit, wird die Wurzel eindeutig. Dadurch ist der Angriff vereitelt (weil der Entschlüssler nur noch die Wurzel zurückliefert, die der Angreifer schon kennt). Dadurch ist die Äquivalenz der Sicherheit zum Rabin-Kryptosystem nicht mehr beweisbar. Allerdings, laut dem Handbook of Applied Cryptography von Menezes, Oorschot und Vanstone,<a href="#cite_note-1">[1]</a> hält die Äquivalenz unter der Annahme, dass das Wurzelziehen ein zweigeteilter Prozess ist (1. Wurzel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mod \ p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mod \ p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/336b169bca657e4f52bcefb131fa128d9f3fafa4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.625ex; height:2.509ex;" alt="{\displaystyle \mod \ p}" loading="lazy"> und Wurzel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mod \ q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mod \ q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/73e8dd5ea49c1130c16a68f801c64e294d72f98a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.525ex; height:2.509ex;" alt="{\displaystyle \mod \ q}" loading="lazy"> ziehen und 2. Chinesischen Restsatzalgorithmus anwenden).

Da bei der Kodierung nur die quadratischen Reste verwendet werden (im Beispiel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=77}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=77}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74da71eb61a45f81899b34a8aff56760f9fc6d4f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.818ex; height:2.176ex;" alt="{\displaystyle n=77}" loading="lazy"> sind das nur 23 der 76 möglichen Zustände), ist das Verfahren zusätzlich angreifbar.

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Johannes Buchmann: Einführung in die Kryptographie, 2., erweiterte Auflage. Springer, Berlin u. a. 2001 ISBN 3-540-41283-2 (S. 125 ff.)</li>

<li>Michael O. Rabin: <a rel="nofollow" class="external text" href="http://www.lcs.mit.edu/publications/specpub.php?id=780">Digitalized Signatures and Public-Key Functions as Intractable as Factorization</a>. MIT-LCS-TR 212, MIT Laboratory for Computer Science, Januar 1979 (englischer Originalaufsatz)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> <a rel="nofollow" class="external text" href="http://cacr.uwaterloo.ca/hac/">Handbook of Applied Cryptography.</a> Abgerufen am 23. Mai 2006 (englisch).<span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3ARabin-Kryptosystem&rft.title=Handbook+of+Applied+Cryptography&rft.description=Handbook+of+Applied+Cryptography&rft.identifier=http%3A%2F%2Fcacr.uwaterloo.ca%2Fhac%2F&rft.date=&rft.language=en">

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2026-01-02" href="https://de.wikipedia.org/wiki/?title=Rabin-Kryptosystem&oldid=262971105">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>